from collections import deque


def max_sliding_window(nums, win_size):
    N = len(nums)
    res = []
    if N == 0 or win_size < 1:
        return res

    index_queue = deque()
    for i in range(N):
        # 以下三行代码把窗口中最大元素的index放到双端队列的首位
        while index_queue and nums[index_queue[-1]] <= nums[i]:
            index_queue.pop()
        index_queue.append(i)

        if i - win_size >= index_queue[0]:  # 此时说明当前的元素已非原窗口所覆盖
            index_queue.popleft()

        if i >= win_size - 1:  # 从窗口大小-1个元素才开始添加最大元素
            res.append(nums[index_queue[0]])
    return res


if __name__ == "__main__":
    nums = [4, 5, 3, 4]
    win_size = 3
    print(max_sliding_window(nums, win_size))



